package xyz.masaikk;

public class NQueensByBlackboard {
	private static int[] queens;
	private static int QNum;
	private static int resultCount;
	private static int row;
	private static int column;

	public NQueensByBlackboard(int QNum) {
		NQueensByBlackboard.QNum = QNum;
		init();
	}

	public int getResultCount() { // ���ؽ����Ŀ
		return resultCount;
	}

	public void init() {
		queens = new int[QNum];
		row = column = resultCount = 0;
		 
		for (int i = 0; i < QNum; i++)	// ��ʼ������
			queens[i] = 0;

		Thread[] threadQueen = new Thread[QNum];	//�����߳�����
		
		int temp = 0;	
		
		while(row >= 0) {
			threadQueen[temp] = new Thread(new SearchQueen());	//��ʼ����һ���߳�
			threadQueen[temp].start();
			
			try {
				threadQueen[temp].join();	//�ȴ���һ���߳����н���	
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
			if(temp + 1 == QNum) temp = -1;	//���ѭ����ϣ��ٴ�ͷ��ʼ
			temp++;
		}
	}

	static class SearchQueen implements Runnable {

		public SearchQueen() {
		}

		@Override
		public void run() {
			put();
		}

		public synchronized void put() {	//���ûʺ�ķ���
			column = queens[row];	//��ȡrow�лʺ������
			while (column < QNum) {
				if(row == 0) {	//��һ�лʺ�λ�ò��ü��
					queens[row] = column;
					break;
				}
				else if (isValid(row, column)) {
					queens[row] = column;
					break;
				}
				column++;
			}
			if (column < QNum) {
				if (row + 1 == QNum) {
					resultCount++;
					queens[row] += 1;
				} else
					queens[++row] = 0;
			} else {
				row--;
				if (row >= 0)
					queens[row] += 1;
			}

		}

		private boolean isValid(int row, int column) {
			for (int i = 1; i <= row; i++)
				if (queens[row - i] == column
						|| queens[row - i] == column - i
						|| queens[row - i] == column + i)
					return false;
			return true;
		}
	}
}

class main{
	public static void main(String[] args) {
		NQueensByBlackboard nq=new NQueensByBlackboard(8);
		System.out.println(nq.getResultCount());
	}
}
